import java.util.LinkedHashMap;
import java.util.Map;

class EncapLRUCache<K,V> {
    private Map<K,V> cache;
    private int cacheSize;

    public EncapLRUCache(int cSize){
        cache=new LinkedHashMap<>(cSize);
        cacheSize=cSize;
    }

    private void maintain(K key, V val){
        cache.remove(key);
        cache.put(key,val);
    }

    public V get(K key){
        V val = cache.get(key);
        if(val != null){
            maintain(key, val);
        }
        return val;
    }

    public void put(K key,V val){
        maintain(key, val);
        while(cache.size() > cacheSize){
            cache.remove(cache.keySet().iterator().next());
        }
    }

}
